// 最接近目标值的子序列和
// 给你一个整数数组 nums 和一个目标值 goal
// 你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal
// 也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal)
// 返回 abs(sum - goal) 可能的 最小值
// 注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
// 数据量描述:
// 1 <= nums.length <= 40
// -10^7 <= nums[i] <= 10^7
// -10^9 <= goal <= 10^9
// 测试链接 : https://leetcode.cn/problems/closest-subsequence-sum/

class Solution 
{
    static const int MAXN = 1 << 20;
    int lsum[MAXN];
    int rsum[MAXN];
    int fill; // 填充到哪

    // e：结束边界, i：当前遍历到的位置，s：累加和，fill：填充数组的下标
    void collect(vector<int>& nums, int i, int e, int s, int* sum)
    {
        if(i == e) sum[fill++] = s;
        else
        {
            // nums[i...] 这一组相同的数字有几个
            int j = i + 1;
            // nums[ 1 1 1 1 1 2 ....]
            //       i         j   
            while(j < e && nums[j] == nums[i]) ++j;
            for(int k = 0; k <= j - i; ++k)
            {
                collect(nums, j, e, s + k * nums[i], sum);
            }
        }
    }

public:
    int minAbsDifference(vector<int>& nums, int goal) 
    {
        int n = nums.size();
        int mn = 0, mx = 0;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] >= 0) mx += nums[i];
            else mn += nums[i];
        }

        // 如果全部的正数加起来都比 goal 小，那么直接返回 abs(mx - goal)
        if(mx < goal) return abs(mx - goal);
        // 如果全部的负数加起来都比 goal 大，那么直接返回 abs(mn - goal)
        if(mn > goal) return abs(mn - goal);

        // 由于本题的子序列跟顺序是无关的，所以对原始数组进行排序
        // 这样后面递归的时候，还能剪枝（常数优化）
        sort(nums.begin(), nums.end());
        fill = 0;
        collect(nums, 0, n >> 1, 0, lsum);
        int lsize = fill;
        fill = 0;
        collect(nums, n >> 1, n, 0, rsum);
        int rsize = fill;

        // 排序 + 双指针
        sort(lsum, lsum + lsize);
        sort(rsum, rsum + rsize);
        int ans = abs(goal);
        for(int i = 0, j = rsize - 1; i < lsize; ++i)
        {
            while(j > 0 && abs(goal - lsum[i] - rsum[j - 1]) <= abs(goal - lsum[i] - rsum[j])) --j;
            ans = min(ans, abs(goal - lsum[i] - rsum[j]));
        }
        return ans;
    }
};